The ability to cut out objects from a greater image setting, such as may be found in a computing device in a computer system, has numerous industrial and consumer applications. For instance, in a security setting, it may be desirable to isolate a vehicle, and its two-dimensional (2-D) outline, for purposes of tracking the vehicle from frame to frame as the vehicle moves. Similarly, one could imagine the tracking of a basketball or the like, as it moves around in a basketball game, for purposes of moving a camera. Marketing applications may include a task of assembling a variety of different, or disparate, media sources to form a unique marketing message, and thus there may be a need for cutting out certain objects from one media source to include, or superimpose, in another media source. Consumers alike may wish to cutout portions of photographs, or other media content, for personal use, e.g., to cutout the family dog from a digital photograph and superimpose the family dog next to the family cat.
In short, there are an increasing number of digital images available just about anywhere, when one considers the Internet as a source of multimedia digital content, the increasing use and exchange of digital photographs and the ability to transform analog representations of images to corresponding digital representations. FIG. 1 illustrates an exemplary image 200 in connection with which it may be desirable to define the boundary of an object 210. In this case, the object 210 is a cheetah and the strong texturing of the foreground, i.e., the cheetah's pelt, makes the task of image object cut-out a difficult task. While human eyes coupled to a human brain can intuitively separate the cheetah 210 from the background 220 in three dimensions, computers are less intuitively inclined, and are restricted to instructions given to them for interpreting the two-dimensional arrays of color pixels, or two-dimensional array of black and white pixels.
The extraction of a region of interest from one image to be pasted into another image is thus a fundamental and difficult image editing capability. This editing task is generally divided into three elementary steps. First, a region of interest is selected. Second, the foreground region, represented by a field of RGB-values and an α-mask, is extracted from the source image, while paying particular attention to mixed pixels on the region boundary. Third, the textured foreground is pasted onto the new background, using the α-mask. For a variety of reasons, present methods for performing the first part of the process, namely foreground region selection, are inadequate.
Thus, there is a need for a new interactive method for constructing a bounding curve for the foreground. Optimal automatic detection of image boundaries has been studied to some degree and some solutions have been proposed. For instance, one present day system has developed a dynamic programming algorithm for extraction boundaries by optimizing a cost function measuring a combination of intrinsic and extrinsic properties. Another present day system approached the same kind of optimization problem using a form of heuristic search.
Another such system borrowed the machinery of probabilistic multi-target tracking to develop a curve following algorithm that deals with branching. More recently, the problem of automatic tracking of roads in images has been addressed using a probabilistic decision tree algorithm based on likelihood ratio tests, and by applying a particle filter. However, no existing system has adapted such particle filtering techniques to the interactive problem of image cut-out. Thus, presently, no one has developed a system that performs automatic optimal curve detection by particle filtering.
Achieving high quality cut-out is difficult in practice because the foreground boundary needs to be located accurately, to within a pixel or better. Marking individual pixels by hand can be accurate, but is laborious and thus can only be done properly at a snail's pace. Semi-automatic methods can speed up the process, but they have to rely on assumptions about the shape properties of the bounding contour, whose validity is somewhat specific to a particular contour. Thus, there is a need for a more robust approach to the problem of image cut-out, whereby a box of tools is provided to and selected by the user, on a problem-by-problem basis. Some commonly provided pre-existing tools include: Freeform curve drawing, the use of region properties, curve snapping, snakes and “intelligent scissors.”
Freeform curve drawing relates to a technique wherein a curve is constructed explicitly, either as a mathematical curve, e.g. a parametric spline, or pixel by pixel, giving the user maximum control, but also maximum labor. Tools that work using region properties, such as ADOBE's® Magic Wand and similar tools, work on an entirely different principle. Rather than using boundary properties, these tools use region properties, extending the color profile of seed regions; a related technique is known as key extraction. Curve snapping is used to accelerate the drawing of boundaries by snapping the cursor towards detected image features such as edges and corners. This saves labor wherever the image features are sufficiently well defined for reliable, automatic detection. The snakes algorithms allow an initial, approximately drawn, bounding curve to be refined globally, taking into account both extrinsic properties such as the degree of coincidence with detected image features, and intrinsic properties such as smoothness. Smoothness is encouraged by penalizing curvature in a cost function for the fitted curve. The snakes algorithms can save even more labor, but the inbuilt tendency to smoothness is not appropriate in all situations. “Intelligent Scissors” techniques, such as Livewire, minimize a combined cost based on various extrinsic properties but does so serially, by dynamic programming (DP), starting at one end of the curve. In this way, intrinsic properties are taken into account and the serial construction fits well with the way humans draw; however, in practice the use of DP restricts the intrinsic properties, i.e., curve length can be taken into account, but not curve smoothness.
Thus, there is a need for a robust mechanism or component that provides boundary definition of an object in an image for purposes of selecting a region of interest. In this regard, it would be advantageous to provide a tool that includes the desirable results or elements of both the snake algorithms and the “intelligent scissors” techniques, described above. Like the snake algorithms, it would be advantageous to provide a tool that incorporates curve smoothness, not just curve length. Like the “intelligent scissors” techniques, it would be advantageous to provide a tool that constructs a boundary for the object serially, i.e., by beginning at one point, or end, of the curve and building the boundary curve from that point. It would be still further desirable to use approximate cost minimization algorithms, such as Monte Carlo algorithms to aid in the minimization of computation necessary to achieve these goals, thereby providing a real-time solution to the problem of image boundary definition.